package vn.com.epi.algorithm.clustering;

import java.util.ArrayList;
import java.util.List;
import java.util.Random;

public class KMeans {
	
	private static final int MIN_ELEMENTS = 30;
	
	public static int n;
	public static int maxElements;
	public static int kClusters;
	public static int numIterators;
	private double maxSimilarity;
	private int[] means;
	private AVLTree<Pair> tree;	
	private int[] clusterID;
	private int[] deg;
	public int[] label;
	public List<Integer>[] cluster;	
	public KMeans() {
		
	}

	public KMeans(int n_, int k, int it, int[] lb) {
		n = n_;
		maxElements = n/2;
		kClusters = k;
		numIterators = it;
		means = new int[kClusters];
		label = new int[n];		
		clusterID = new int[n];				
		deg = new int[kClusters];
		for (int i = 0; i < n; i++)
			label[i] = lb[i];
	}
	
	private float distance(int u, int v) {
		int i, j;
		float sum;
		u = label[u];
		v = label[v];
		i = 0;
		j = 0;
		sum = 0;		
		while (i < Data.users[u].size() && j < Data.users[v].size()) {
			if (Data.users[u].get(i).getIndex() == Data.users[v].get(j).getIndex()) {
				sum += Math.min(Data.users[u].get(i).getValue(), Data.users[v].get(j).getValue());
				i++;
				j++;
			} else if (Data.users[u].get(i).getIndex() < Data.users[v].get(j).getIndex()) 
				i++;
			else 
				j++;
		}
		return sum / (Data.total[u] + Data.total[v] - sum);
	}
	
	private void reset() {
		for (int i = 0; i < kClusters; i++) 
			deg[i] = 0;
	}

	@SuppressWarnings("unchecked")
	public void approximateAlgorithm() {

		Random rand = new Random(System.currentTimeMillis());
		float[] d = new float[n];
		float[] maxD = new float[n];
		boolean[] visited = new boolean[n];
		int[] clusterID_ = new int[n];
		int[] means_ = new int[kClusters];
		maxSimilarity = 0;
		for (int it = 0; it < numIterators; it++) {

			int first;
			first = rand.nextInt(n);
		
			tree = new AVLTree<Pair>();
			tree.insert(new Pair(first, 0));
			int count = 0;
			for (int i = 0; i < n; i++) {
				visited[i] = false;
				d[i] = Float.MAX_VALUE;
				maxD[i] = 0;
				clusterID_[i] = -1;
			}
			d[first] = 0;
			reset();
			while (!tree.isEmpty()) {
				Pair top = tree.getSmallest().getElement();
				int u = top.getKey();
				maxD[u] = 0;
				visited[u] = true;
				means_[count] = u;
				tree.delete(top);
				clusterID_[u] = count;
				for (int v = 0; v < n; v++) {
					if (!visited[v]) {
						float dist = distance(u, v);
						if (dist > maxD[v] || (dist == maxD[v] && clusterID_[v] == -1)) {							
							deg[clusterID_[u]]++;
							if (clusterID_[v] > -1) 
								deg[clusterID_[v]]--;
							clusterID_[v] = count;
							maxD[v] = dist;
						}
						if (d[v] > dist) {
							Pair element = new Pair(v, d[v]);
							tree.delete(element);
							d[v] = dist;
							Pair newItem = new Pair(v, d[v]);
							tree.insert(newItem);
						}
					}
					if (deg[clusterID_[u]] >= maxElements)
						break;
				}
				count++;
				if (count == kClusters)
					break;
			}
			tree = null;
			for (int v = 0; v < n; v++)
				if (clusterID_[v] == -1) {
					clusterID_[v] = rand.nextInt(kClusters);
					maxD[v] = distance(v, means_[clusterID_[v]]);
				}
			
			double sumSimilarity = 0;
			for (int i = 0; i < n; i++)
				sumSimilarity += maxD[i];
			if (maxSimilarity < sumSimilarity) {
				maxSimilarity = sumSimilarity;
				for (int i = 0; i < n; i++) 
					clusterID[i] = clusterID_[i];			
				for (int i = 0; i < kClusters; i++) 
					means[i] = means_[i];
			}
		}
		tree = null;

//		System.out.println("min distance: " + maxSimilarity);
//		System.out.println("Danh sach tam cum: ");
//		for (int i: means) {
//			System.out.print(i + " ");
//		}
		reset();
		for (int i = 0; i < n; i++) {
//			System.out.println(i+ "\t" + clusterID[i] + "\t" + distance(i, means[clusterID[i]]));
			deg[clusterID[i]]++;
		}
		process();		
		cluster = new List[kClusters];
		for (int i = 0; i < kClusters; i++)
			cluster[i] = new ArrayList<Integer>();
		for (int i = 0; i < n; i++) {		
			deg[clusterID[i]]++;
			cluster[clusterID[i]].add(i);
		}
//		for (int i = 0; i < kClusters; i++)
//			System.out.println(i + ":\t" + deg[i]);
	}
	
	public void process() {
//		System.out.println("number of clusters: " + kClusters);
		boolean[] invalid = new boolean[kClusters];
		int[] id = new int[kClusters];
		int sub = 0;		
		for (int i = 0; i < kClusters; i++) 
			if (deg[i] < MIN_ELEMENTS) {
				sub++;
				invalid[i] = true;
			} else 
				invalid[i] = false;
		int index = -1;
//		System.out.println(sub);
		for (int i = 0; i < kClusters - sub; i++) {
			do {
				index++;
			} while (invalid[index]);
			id[index] = i;
		}
				
		for (int i = 0; i < n; i++)
			if (invalid[clusterID[i]]) {
				double maxSim = 0;
				for (int j = 0; j < kClusters; j++) {
					double d = distance(i, means[j]);
					if (!invalid[j] && maxSim <  d) {
						maxSim = d;
						clusterID[i] = j;
					}
				}
			}
		
		for (int i = 0; i < n; i++)
			clusterID[i] = id[clusterID[i]];
		kClusters -= sub;
		reset();
	}
	
	public static double getHeapUsed() {
		int mb = 1024*1024;         
        Runtime runtime = Runtime.getRuntime();
        double used = (runtime.totalMemory() - runtime.freeMemory()) / mb;
        return used;
	}
	
	public static double getHeapUsedByte() {
        Runtime runtime = Runtime.getRuntime();
        double used = (runtime.totalMemory() - runtime.freeMemory());
        return used;
	}
	
	public void test(int n_) {
		Random rand = new Random(System.currentTimeMillis());
		new Data(n_); // create database
//		for (int i = 0; i < n_; i++) {
//			int k = 15 + rand.nextInt(5);
//			boolean[] b = new boolean[20];
//			for (int j = 0; j < 20; j++)
//				b[j] = false;
//			for (int j = 0; j < k; j++) {
//				int r = rand.nextInt(20);
//				if (!b[r]) {
//					int p = rand.nextInt(10);
//					add(i, r, p);
//					b[r] = true;
//				}
//			}
//		}
		for (int i = 0; i < n_; i++) {
			int d = 40;
			for (short j = 0; j < d; j++) {
				int state = rand.nextInt(3);
				short p;
				if (state == 0)
					p = 0;
				else
					p = (short)rand.nextInt(10);
				Data.add(i, j, p);
				double heap = getHeapUsed(); 
				if (heap > 300)
					System.out.println("Heap: " + heap);
					
			}
		}		
		long start = System.currentTimeMillis();
		Data.initial();
		approximateAlgorithm();
		long end = System.currentTimeMillis();
		System.out.print("Total time used: " + (end - start) + " ms");
	}
	
	public static void main(String[] args) {
//		KMeans kmeans = new KMeans(6, 2);
//		kmeans.add(0, 1, 1);
//		kmeans.add(0, 2, 1);
//		kmeans.add(1, 1, 2);
//		kmeans.add(1, 2, 2);
//		kmeans.add(2, 1, 5);
//		kmeans.add(2, 2, 5);
//		kmeans.add(3, 1, 6);
//		kmeans.add(3, 2, 6);
//		kmeans.add(4, 1, 7);
//		kmeans.add(4, 2, 7);
//		kmeans.add(5, 1, 1);
//		kmeans.add(5, 2, 1);
//		kmeans.initial();
//		kmeans.approximateAlgorithm();
		
		int nn = 100000;
		int[] label = new int[nn];
		for (int i = 0; i < nn; i++)
			label[i] = i;
		KMeans kmeans = new KMeans(nn, 10, 10, label);
		kmeans.test(nn);

//		AVLTree<Pair> tree = new AVLTree<Pair>();
//		tree.insert(new Pair(1, 1));
//		tree.insert(new Pair(2, 2));
//		tree.insert(new Pair(3, 3));
//		Pair p = tree.getSmallest().getElement();
//		System.out.println(p);
//		tree.delete(p);
//		p = tree.getSmallest().getElement();
//		System.out.println(p);
		}

}
